作者：Yu仙笙真滴卷😎
专栏：CSP-J初赛真题🏀
目录
一、单项选择题（共15题，共计30分）
二、阅读程序（程序输入不超过数组或字符串定义的范围，共计40分）
（一）
解析：
（二）
解析：
（3）
解析：
三、完善程序
（一）
有n个人围成一个圈，一次标号0至n-1，从0号开始，依次0，1，0，1，. . . . 交替报数，报道1 的人会离开，直至圈中只剩下一个人，求最后剩下人的编号。
试补全模拟程序
解析：
（二）
（矩形计数）平面上有n个关键点，求有多少个四条边都和x轴或者y轴平行的矩形，满足四个顶点都是关键点。给出的关键点可能有重复，但完全重合的矩形只计一次。
试补全枚举算法。
解析：
一、单项选择题（共15题，共计30分）---------------------------------------------------------------------------------------------------------------------------------
1.以下不属于面向对象程序设计语言的是（D）。
A.C++ B.Python C.Java D.C
题目解析
正确答案： D，C语言是面向过程的编译性语言
---------------------------------------------------------------------------------------------------------------------------------
2.以下奖项与计算机领域最相关的是（B）。
A.奥斯卡奖 B.图灵奖 C.诺贝尔奖 D.普利策奖
题目解析
正确答案： B，图灵奖是计算机领域的国际最高奖项
---------------------------------------------------------------------------------------------------------------------------------
3.目前主流的计算机储存数据最终都是转换成（A）数据进行存储。
A.二进制 B.十进制 C.八进制 D.十六进制
题目解析
正确答案： A，计算机中以二进制方式存储数据
---------------------------------------------------------------------------------------------------------------------------------
4.以比较作为基本运算，在N个数中找出最大数，最坏情况下所需要的最少的比较次数为（C）。
A.N2 B.N C.N-1 D.N+1
题目解析
正确答案： C, 最值问题，以第一个数作为初始值，从第二个数开始比较，最坏情况下要比较到序列末尾才能得到最大值，即比较 N−1 次
---------------------------------------------------------------------------------------------------------------------------------
5.对于入栈顺序为a,b,c,d,e的序列，下列（D）不是合法的出栈序列。
A.a,b,c,d,e B.e,d,c,b,a C.b,a,c,d,e D.c,d,a,e,b
题目解析
正确答案： D, acb进栈，c出栈，d进栈出栈，之后从栈顶到栈底还有b,a没有出栈，a无法在b之前先出栈
---------------------------------------------------------------------------------------------------------------------------------
6.对于有n个顶点，m条边的无向连通图（m>n），需要删掉（D）条边才能使其称为一棵树。
A.n-1 B.m-n C.m-n-1 D.m-n+1
题目解析
正确答案： D, n个顶点的树有n−1条边，需删除 m-(n-1)= m-n+1 条边
---------------------------------------------------------------------------------------------------------------------------------
7.二进制数101.11对应的十进制数是（C）。
A.6.5 B.5.5 C.5.75 D.5.25
---------------------------------------------------------------------------------------------------------------------------------
8.如果一棵二叉树只有根结点，那么这棵二叉树高度为1。请问高度为5的完全二叉树有（A）种不同的形态？
A.16 B.15 C.17 D.32
题目解析
正确答案： A, h=5的完全二叉树共有 24 个节点，第五层最少1个节点，最多16个节点，因此一共有16种情况
---------------------------------------------------------------------------------------------------------------------------------
9.表达式a*(b+c)*d的后缀表达式为（B），其中“*”和“+”是运算符。
A.**a+bcd B.abc+*d* C.abc+d** D.*a*+bcd
题目解析
正确答案： B, 考察前后缀表达式。表示为( a [ bc +] * ) d *，后缀表达式为 abc+*d*
---------------------------------------------------------------------------------------------------------------------------------
10.6个人，两个人组一队，总共组成三队，不区分队伍的编号，不同的组队情况有（B）。
A.10 B.15 C.30 D.20
---------------------------------------------------------------------------------------------------------------------------------
11.在数据压缩编码种的哈夫曼编码方法，在本质是一种（B）的策略。
A.枚举 B.贪心 C.递归 D.动态规划
题目解析
正确答案： B, 哈夫曼编码每次把频率最低的两个节点合并，产生新的节点并放在集合中，删除用来合并的两个节点，重复这个过程直到剩下一个节点为止。每次选择频率最小的两个节点就是贪心的思想。
---------------------------------------------------------------------------------------------------------------------------------
12.由1，1，2，2，3这五个数字组成不同的三位数有（A）种。
A.18 B.15 C.12 D.24
题目解析
正确答案： A, 枚举法，不同的三位数有：321，322，311，312，211，212，213， 221， 223，231， 232， 112，113，121，122，123，131，132共十八种
---------------------------------------------------------------------------------------------------------------------------------
13.考虑如下递归算法
solve(n) if n=5 return n*solve(n-2) else return n*solve(n-1)则调用solve(7)得到的返回结果为（C）。
A.105 B.840 C.210 D.420
---------------------------------------------------------------------------------------------------------------------------------
14.以a为起点，对右边的无向图进行深度优先遍历，则b,c,d,e四个点中有可能作为最后一个遍历到的点的个数为（B）。
A.1 B.2 C.3 D.4
题目解析
正确答案： B，从a→b方向的遍历：a−b−d−c−e; 从a→c方向的遍历：a-c-e-d-b和a−c−d−b−e. 则最多有两个终点：e和b
---------------------------------------------------------------------------------------------------------------------------------
15.有四个人要从A点坐一条船过河到B点，船一开始在A点。该船一次最多可坐两个人。已知这四个人中每个人独自坐船的过河时间分别为1，2，4，8，且两个人坐船的过河时间为两人独自过河时间的较大者。则最短（B）时间可以让四个人过河到B点（包括从B点把船开回A点的时间）。
A.14 B.15 C.16 D.17
题目解析
正确答案： B, 1和2从 A→B，1从B→A，此时A点有1,4,8 ; B点有2，所用时间：2+1=3； 4和8从A→B，2从B→A。此时A点有1,2; B点有4,8，所用时间：8+2=10； 最后1和2从A→B，所用时间为2；总时间为3+10+2=15
---------------------------------------------------------------------------------------------------------------------------------
二、阅读程序（程序输入不超过数组或字符串定义的范围，共计40分） （一） 01 #include 02 03 int n;04 int a[1000];05 06 int f(int x)07 {08 int ret = 0;09 for(; x; x &= x - 1) ret ++;10 return ret;11 }12 13 int g(int x)14 {15 return x & - x;16 }17 18 int main()19 {20 scanf("%d", &n);21 for (int i = 0; i < n; i++) scanf("%d", &a[i]);22 for (int i = 0; i < n; i++)23 printf("%d ", f(a[i]) + g(a[i]));24 printf("\n");25 return 0;26 }---------------------------------------------------------------------------------------------------------------------------------
16.输入的n等于1001时，程序不会发生下标越界。这句话描述是否正确？B
A.正确 B.错误
---------------------------------------------------------------------------------------------------------------------------------
17.输入的a[i]必须全为正整数，否则程序将陷入死循环。这句话的描述是否正确？B
A.正确 B.错误
---------------------------------------------------------------------------------------------------------------------------------
18.当输入为“5 2 11 9 16 10”时，输出为“3 4 3 17 5”。这句话的描述是否正确？B
A.正确 B.错误
---------------------------------------------------------------------------------------------------------------------------------
19.当输入为“1 511998”时，输出为“18”。这句话的描述是否正确？A
A.正确 B.错误
---------------------------------------------------------------------------------------------------------------------------------
20.将源代码中g函数的定义（13-16行）移到main函数的后面，程序可以正常编译运行。这句话的描述是否正确？B
A.正确 B.错误
---------------------------------------------------------------------------------------------------------------------------------
21.当输入为“2 -65536 2147483647”时，输出为（B）
A."65532 33" B."65552 32" C."65535 34" D."65554 33"
---------------------------------------------------------------------------------------------------------------------------------
解析：题目解析
解析： 综述：本题考察位运算及进制转换相关知识。 &代表按位与，即将参与运算的两数均转换为二进制后逐位进行与运算。只有当参与运算的对应两位均为1时，结果对应位才为1。例如：88 &11=(1000)_211=(1000)2 & (1011)_2=(1000)_2=8(1011)2=(1000)2=8 对于f(x)f(x)：思考二进制中借位过程，本质上是将被借位变为0，并将被借位右侧直至借位者位置的0全部变为1。更具体地，我们可以将xx写成(A)1(B)(A)1(B)形式，B代表nn个0，即A与B中间的1为xx从右向左数第一个1。则x-1x−1将为(A)0(C)(A)0(C)形式，C代表nn个1。参考按位与定义，则xx & (x-1)=(A)0(B)(x−1)=(A)0(B)。所以本质上xx&=(x-1)=(x−1)的作用为将xx的最右侧的1变为0。每次循环会将一个1变为0，循环终止条件为xx变为0，则实际上retret统计的就是xx二进制表示中1的数目。 对于g(x)g(x)：返回xx&(-x)(−x)。负数在计算机中的表示为原正数二进制取反后+1。如10的二进制表示为0000 1010，其取反后为1111 0101。1111 0101+1=1111 011011110101+1=11110110。即-10的二进制表示为1111 0110。 不难发现，+1这个行为会导致进位。具体地，+1会将取反后二进制数码中最右端的所有1（由于进位）变为0，并将取反后二进制数码中从右边数第一个0变为1。又由于取反，在原二进制中对应从右边数第一个0的位置的数，实际上就为从右边数的第一个1（右边全为0）。综上可以发现，一个数与他的的相反数在二进制中，从右向左直到第一个1为止都是相同的，而在从右向左数第一个1的左侧，该数与其相反数的每一位二进制数码均相反。因此，xx&(-x)(−x)将得到除了在原数中最右侧的1的位置为1，其余位置全为0的二进制数。 如：0100 000001000000 & [-(0100 0000)]=0100 0000[−(01000000)]=01000000 & 1100 0000=0100 000011000000=01000000 实际上，由此可得当一个偶数与他的负值相与时结果是能被这个偶数整除的最大的2的nn次幂；当一个奇数与他的负值相与时结果一定是1. 1.aa数组的大小为1000，因此下标为0~999,1001越界 2.f(x)f(x)与在xx为正整数与负整数时均可正常运作，不会进入死循环，错误 3.最后输出为 f(a[i])+g(a[i])f(a[i])+g(a[i]) 形式。当输入5（二进制为101）时：1的个数为2个，则 f(a[i])=2f(a[i])=2；最低位的1表示为1，则g(a[i])=2g(a[i])=2 ；则输出为(2+1=3)(2+1=3). 以此类推… 然而当输入为10（二进制为1010）时， f(a[i])=2, g(a[i])=2f(a[i])=2,g(a[i])=2 ;则输出为（2+2=42+2=4），不应该为5 4.考察进制转换。511998的二进制表示为111 1100 1111 1111 1110，所以f(511998)=16,g(511998)=2f(511998)=16,g(511998)=2，输出18，正确。 5.若要将函数移动至mainmain函数后面，则需要先在mainmain前进行